import generator
#插入排序：
def insertionSort(arr):
    for i in range(1, len(arr)): 
        key = arr[i] 
        j = i-1
        while j >=0 and key < arr[j] : 
            arr[j+1] = arr[j] 
            j -= 1
        arr[j+1] = key
    return arr


#堆排序
# coding=utf-8
def heap_sort(array):
    first = len(array) 
    for start in range(first, -1, -1):
        # 从下到上，从右到左对每个非叶节点进行调整，循环构建成大顶堆
        big_heap(array, start, len(array) - 1)
    for end in range(len(array) - 1, 0, -1):
        # 交换堆顶和堆尾的数据
        array[0], array[end] = array[end], array[0]
        # 重新调整完全二叉树，构造成大顶堆
        big_heap(array, 0, end - 1)
    return array
 
 
def big_heap(array, start, end):
    root = start
    # 左孩子的索引
    child = root * 2 + 1
    while child <= end:
        # 节点有右子节点，并且右子节点的值大于左子节点，则将child变为右子节点的索引
        if child + 1 <= end and array[child] < array[child + 1]:
            child += 1
        if array[root] < array[child]:
            # 交换节点与子节点中较大者的值
            array[root], array[child] = array[child], array[root]
            # 交换值后，如果存在孙节点，则将root设置为子节点，继续与孙节点进行比较
            root = child
            child = root * 2 + 1
        else:
            break

        
 #冒泡排序

def bubbleSort(arr):
    n = len(arr)
    # 遍历所有数组元素
    for i in range(n):
        # Last i elements are already in place
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

#二分归并排序

def merge(a,b):
    l=[]
    f=s=0
    while f<len(a) and s<len(b):
        if a[f]<b[s]:
            l.append(a[f])
            f+=1
        else:
            l.append(b[s])
            s+=1
 
    #如果a遍历完 b还有余下值没有和a中元素比较则
    if f==len(a):
        for i in b[s:]:       #巧用for循环遍历b中余下元素
            l.append(i)
 
    else:
        for i in a[f:]:
            l.append(i)
    return l                #归一新数组


def sort_merge(lists):      #针对大数组分化为最小数量级
    if len(lists)<=1:
        return lists
    middle=len(lists)//2
    left=sort_merge(lists[:middle])
    right=sort_merge(lists[middle:])
    return merge(left,right)


#快速排序

def quick_sort(lists,i,j):
    if i >= j:
        return list
    pivot = lists[i]
    low = i
    high = j
    while i < j:
        while i < j and lists[j] >= pivot:
            j -= 1
        lists[i]=lists[j]
        while i < j and lists[i] <=pivot:
            i += 1
        lists[j]=lists[i]
    lists[j] = pivot
    quick_sort(lists,low,i-1)
    quick_sort(lists,i+1,high)
    return lists